import java.util.Arrays;

/**
 * Created with IntelliJ IDEA
 * Description:
 * User: Administrator
 * Data: 2023 - 09 - 09
 * Time: 21:21
 */
//牛客 矩阵最长递增路径  调试看看自己错在哪
public class Solution5 {
    //法一 官方推荐方法dfs
    static int m, n;
    static int[] dx = new int[]{0, 0, -1, 1};//dx和dy一一对应i、j下标元素的左右上下
    static int[] dy = new int[]{-1, 1, 0, 0};
    static int[][] memo;
    public static int solve (int[][] matrix) {
        int ret = 0;//这里ret初始化为0或1均可
        m = matrix.length;
        n = matrix[0].length;
        memo = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                ret = Math.max(ret, dfs(matrix, i, j));
            }
        }
        return ret;
    }
    //每个下标里的元素做的都是看看以自己为起点的最长递增路径是多少，再这个过程中不断更新以自己为起点的左右上下方向的最长递增路径
    public static int dfs(int[][] matrix, int i, int j) {//这里递归函数设计成有返回值
        if(memo[i][j] != 0) {
            return memo[i][j];
        }
        int ret = 1;//ret要初始化为1，因为以自己为起点的最长递增路径，自己也算是路径上的一个点
        for (int k = 0; k < 4; k++) {//有了for循环相当于有了递归出口。也可以不写递归出口，但不写上面的递归出口，下面递归的时间复杂度会过大。写了递归出口相当于可以提前结束递归
            int x = i + dx[k], y = j + dy[k];
            if(x >= 0 && x < m && y >= 0 && y < n && matrix[i][j] < matrix[x][y]) {
                ret = Math.max(ret, dfs(matrix, x, y) + 1);//dfs(matrix, x, y)表示以x、y为起点的最长递增路径，同时要加上本层matrix[i][j]这个点(即要加上自己)，所以要dfs(matrix, x, y)+1
            }
        }
        memo[i][j] = ret;
        return ret;
    }
}
